package 笔试.华为.线下面试;

import java.util.Arrays;
import java.util.HashMap;

public class a560和为K的子数组 {
    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        int[] nums = {1, 1, 1};
        int k = 2;
        System.out.println(solution.subarraySum(nums, k));
    }

    static class Solution {
        public int subarraySum(int[] nums, int k) {
            int len = nums.length;
            int[] preSum = new int[len + 1];
            preSum[1] = nums[0];
            for (int i = 2; i <= len; i++) {
                preSum[i] = nums[i - 1] + preSum[i - 1];
            }
            System.out.println(Arrays.toString(preSum));
            int cnt = 0;
            for (int i = 0; i <= len - 1; i++) {
                for (int j = i + 1; j <= len; j++) {
                    if (preSum[j] - preSum[i] == k) {
                        cnt++;
                    }
                }
            }
            return cnt;
        }
    }

    static class Solution2 {
        public int subarraySum(int[] nums, int k) {
            int cnt = 0, preSum = 0;
            HashMap<Integer, Integer> hm = new HashMap<>();
            hm.put(0, 1);
            for (int i = 0; i < nums.length; i++) {
                preSum += nums[i];
                if (hm.containsKey(preSum - k)) { // preSum - ( preSum - k ) == k
                    cnt += hm.get(preSum - k);
                }
                hm.merge(preSum, 1, Integer::sum);
            }
            return cnt;
        }
    }
}
